0874. 模拟行走机器人【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 模拟 + 哈希集合

1. 📝 题目描述

• leetcode

机器人在一个无限大小的 XY 网格平面上行走，从点 (0, 0) 处开始出发，面向北方。该机器人可以接收以下三种类型的命令 commands ：

• -2 ：向左转 90 度
• -1 ：向右转 90 度
• 1 <= x <= 9 ：向前移动 x 个单位长度

在网格上有一些格子被视为障碍物 obstacles。第 i 个障碍物位于网格点 obstacles[i] = (xi, yi)。

机器人无法走到障碍物上，它将会停留在障碍物的前一个网格方块上，并继续执行下一个命令。

返回机器人距离原点的 最大欧式距离 的 平方。（即，如果距离为 5，则返回 25 ）

注意：

• 北方表示 +Y 方向。
• 东方表示 +X 方向。
• 南方表示 -Y 方向。
• 西方表示 -X 方向。
• 原点 [0, 0] 可能会有障碍物。

---

示例 1：

输入：commands = [4,-1,3], obstacles = []
输出：25
解释：
机器人开始位于 (0, 0)：
1. 向北移动 4 个单位，到达 (0, 4)
2. 右转
3. 向东移动 3 个单位，到达 (3, 4)
距离原点最远的是 (3, 4)，距离为 32 + 42 = 25

示例 2：

输入：commands = [4,-1,4,-2,4], obstacles = [[2,4]]
输出：65
解释：机器人开始位于 (0, 0)：
1. 向北移动 4 个单位，到达 (0, 4)
2. 右转
3. 向东移动 1 个单位，然后被位于 (2, 4) 的障碍物阻挡，机器人停在 (1, 4)
4. 左转
5. 向北走 4 个单位，到达 (1, 8)
距离原点最远的是 (1, 8)，距离为 12 + 82 = 65

示例 3：

输入：commands = [6,-1,-1,6], obstacles = []
输出：36
解释：机器人开始位于 (0, 0):
1. 向北移动 6 个单位，到达 (0, 6).
2. 右转
3. 右转
4. 向南移动 6 个单位，到达 (0, 0).
机器人距离原点最远的点是 (0, 6)，其距离的平方是 62 = 36 个单位。

---

提示：

• 1 <= commands.length <= 10^4
• commands[i] 的值可以取 -2、-1 或者是范围 [1, 9] 内的一个整数。
• 0 <= obstacles.length <= 10^4
• -3 * 10^4 <= xi, yi <= 3 * 10^4
• 答案保证小于 2^31

2. 🎯 s.1 - 模拟 + 哈希集合

c

#define HASH_SIZE 100003
typedef struct Node { int x, y; struct Node* next; } Node;

unsigned hashFunc(int x, int y) { return ((unsigned)(x * 1000003 + y)) % HASH_SIZE; }

bool contains(Node** table, int x, int y) {
    for (Node* n = table[hashFunc(x, y)]; n; n = n->next)
        if (n->x == x && n->y == y) return true;
    return false;
}

void insert(Node** table, int x, int y) {
    unsigned h = hashFunc(x, y);
    Node* n = (Node*)malloc(sizeof(Node));
    n->x = x; n->y = y; n->next = table[h]; table[h] = n;
}

int robotSim(int* commands, int commandsSize, int** obstacles, int obstaclesSize, int* obstaclesColSize) {
    Node* table[HASH_SIZE];
    memset(table, 0, sizeof(table));
    for (int i = 0; i < obstaclesSize; i++) insert(table, obstacles[i][0], obstacles[i][1]);
    int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
    int x = 0, y = 0, d = 0, res = 0;
    for (int i = 0; i < commandsSize; i++) {
        if (commands[i] == -2) d = (d + 3) % 4;
        else if (commands[i] == -1) d = (d + 1) % 4;
        else {
            for (int j = 0; j < commands[i]; j++) {
                int nx = x + dx[d], ny = y + dy[d];
                if (contains(table, nx, ny)) break;
                x = nx; y = ny;
                int dist = x * x + y * y;
                if (dist > res) res = dist;
            }
        }
    }
    for (int i = 0; i < HASH_SIZE; i++) {
        Node* n = table[i];
        while (n) { Node* t = n->next; free(n); n = t; }
    }
    return res;
}

js

/**
 * @param {number[]} commands
 * @param {number[][]} obstacles
 * @return {number}
 */
var robotSim = function (commands, obstacles) {
  const set = new Set(obstacles.map(([x, y]) => x + ',' + y))
  const dx = [0, 1, 0, -1],
    dy = [1, 0, -1, 0]
  let x = 0,
    y = 0,
    d = 0,
    res = 0
  for (const cmd of commands) {
    if (cmd === -2) d = (d + 3) % 4
    else if (cmd === -1) d = (d + 1) % 4
    else {
      for (let i = 0; i < cmd; i++) {
        const nx = x + dx[d],
          ny = y + dy[d]
        if (set.has(nx + ',' + ny)) break
        x = nx
        y = ny
        res = Math.max(res, x * x + y * y)
      }
    }
  }
  return res
}

py

class Solution:
    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:
        obs = set(map(tuple, obstacles))
        dx, dy = [0, 1, 0, -1], [1, 0, -1, 0]
        x = y = d = res = 0
        for cmd in commands:
            if cmd == -2: d = (d + 3) % 4
            elif cmd == -1: d = (d + 1) % 4
            else:
                for _ in range(cmd):
                    nx, ny = x + dx[d], y + dy[d]
                    if (nx, ny) in obs: break
                    x, y = nx, ny
                    res = max(res, x * x + y * y)
        return res

• 时间复杂度：$O(n+k)$，其中 n 是命令步数之和，k 是障碍物数
• 空间复杂度：$O(k)$

算法思路：

• 用哈希集合存储障碍物位置，用方向数组模拟四个方向
• 每步检查是否撞到障碍物，实时更新最大欧氏距离的平方